Algorithm Implementation/Sorting/Quicksort

From Wikibooks, open books for an open world

Unreviewed changes are displayed on this page

The latest reviewed version was checked on 21 April 2013. There are 8 pending changes awaiting review.

Jump to: navigation, search

Wikipedia has related information at Quicksort

A Wikibookian suggests that Transwiki:Quicksort be merged into this book or chapter.
Discuss whether or not this merger should happen on the discussion page.

Pseudocode[edit]

Iterative version[edit]

 function QuickSort(Array, Left, Right)
 var
     L2, R2, PivotValue
 begin
     Stack.Push(Left, Right);       // pushes Left, and then Right, on to a stack
     while not Stack.Empty do
     begin
         Stack.Pop(Left, Right);    // pops 2 values, storing them in Right and then Left
         repeat
             PivotValue := Array[(Left + Right) div 2];
             L2 := Left;
             R2 := Right;
             repeat
                 while Array[L2] < PivotValue do // scan left partition
                     L2 := L2 + 1;
                 while Array[R2] > PivotValue do // scan right partition
                     R2 := R2 - 1;
                 if L2 <= R2 then
                 begin
                     if L2 != R2 then
                         Swap(Array[L2], Array[R2]);  // swaps the data at L2 and R2
                     L2 := L2 + 1;
                     R2 := R2 - 1;
                 end;
             until L2 >= R2;
             if R2 - Left > Right - L2 then // is left side piece larger?
             begin
                 if Left < R2 then
                     Stack.Push(Left, R2);
                 Left := L2;
             end;
             else
             begin
                 if L2 < Right then // if left side isn't, right side is larger
                     Stack.Push(L2, Right);
                 Right := R2;
             end;
         until Left >= Right;
     end;
 end;

ALGOL 68[edit]

Quick sort in ALGOL 68 using the PAR clause to break the job into multiple threads.

MODE DATA = INT;
 
PROC partition =(REF [] DATA array, PROC (REF DATA, REF DATA) BOOL cmp)INT: (
    INT begin:=LWB array;
    INT end:=UPB array;
    WHILE begin < end DO
         WHILE begin < end DO
            IF cmp(array[begin], array[end]) THEN
                DATA tmp=array[begin];
                array[begin]:=array[end];
                array[end]:=tmp;
                GO TO break while decr end
            FI;
            end -:= 1
         OD;
         break while decr end: SKIP;
         WHILE begin < end DO
            IF cmp(array[begin], array[end]) THEN
                DATA tmp=array[begin];
                array[begin]:=array[end];
                array[end]:=tmp;
                GO TO break while incr begin
            FI;
            begin +:= 1
         OD;
         break while incr begin: SKIP
    OD;
    begin
);
 
PROC qsort=(REF [] DATA array, PROC (REF DATA, REF DATA) BOOL cmp)VOID: (
    IF LWB array < UPB array THEN
        INT i := partition(array, cmp);
        PAR ( # remove PAR for single threaded sort #
          qsort(array[:i-1], cmp),
          qsort(array[i+1:], cmp)
        )
    FI
);
 
PROC cmp=(REF DATA a,b)BOOL: a>b;
 
main:(
  []DATA const l=(5,4,3,2,1);
  [UPB const l]DATA l:=const l;
  qsort(l,cmp);
  printf(($g(3)$,l))
)

AppleScript[edit]

This is a straightforward implementation. It is certainly possible to come up with a more efficient one, but it will probably not be as clear as this one:

 on sort( array, left, right )
     set i to left
     set j to right
     set v to item ( ( left + right ) div 2 ) of array -- pivot
     repeat while ( j > i )
         repeat while ( item i of array < v )
             set i to i + 1
         end repeat
         repeat while ( item j of array > v )
             set j to j - 1
         end repeat
         if ( not i > j ) then
             tell array to set { item i, item j } to { item j, item i } -- swap
             set i to i + 1
             set j to j - 1
         end if
     end repeat 
     if ( left  < j ) then sort( array, left, j  )
     if ( right > i ) then sort( array, i, right )
 end sort

This ARM RISC assembly language implementation for sorting an array of 32-bit integers demonstrates how well quicksort takes advantage of the register model and capabilities of a typical machine instruction set (note that this particular implementation does not meet standard calling conventions and may use more than O(log n) space):

  qsort:  @ Takes three parameters:
        @   a:     Pointer to base of array a to be sorted (arrives in r0)
        @   left:  First of the range of indexes to sort (arrives in r1)
        @   right: One past last of range of indexes to sort (arrives in r2)
        @ This function destroys: r1, r2, r3, r5, r7
        stmfd   sp!, {r4, r6, lr}     @ Save r4 and r6 for caller
        mov     r6, r2                @ r6 <- right
  qsort_tailcall_entry:
        sub     r7, r6, r1            @ If right - left <= 1 (already sorted),
        cmp     r7, #1
        ldmlefd sp!, {r4, r6, pc}     @ Return, restoring r4 and r6
        ldr     r7, [r0, r1, asl #2]  @ r7 <- a[left], gets pivot element
        add     r2, r1, #1            @ l <- left + 1
        mov     r4, r6                @ r <- right
  partition_loop:
        ldr     r3, [r0, r2, asl #2]  @ r3 <- a[l]
        cmp     r3, r7                @ If a[l] <= pivot_element,
        addle   r2, r2, #1            @ ... increment l, and
        ble     partition_test        @ ... continue to next iteration.
        sub     r4, r4, #1            @ Otherwise, decrement r,
        ldr     r5, [r0, r4, asl #2]  @ ... and swap a[l] and a[r].
        str     r5, [r0, r2, asl #2]
        str     r3, [r0, r4, asl #2]
  partition_test:
        cmp     r2, r4                @ If l < r,
        blt     partition_loop        @ ... continue iterating.
  partition_finish:
        sub     r2, r2, #1            @ Decrement l
        ldr     r3, [r0, r2, asl #2]  @ Swap a[l] and pivot
        str     r3, [r0, r1, asl #2]
        str     r7, [r0, r2, asl #2]
        bl      qsort                 @ Call self recursively on left part,
                                      @  with args a (r0), left (r1), r (r2),
                                      @  also preserves r4 and r6
        mov     r1, r4
        b       qsort_tailcall_entry  @ Tail-call self on right part,
                                      @  with args a (r0), l (r1), right (r6)

The call produces 3 words of stack per recursive call and is able to take advantage of its knowledge of its own behavior. A more efficient implementation would sort small ranges by a more efficient method. If an implementation obeying standard calling conventions were needed, a simple wrapper could be written for the initial call to the above function that saves the appropriate registers.

AutoIt v3[edit]

This is a straightforward implementation based on the AppleScript example. It is certainly possible to come up with a more efficient one, but it will probably not be as clear as this one:

  Func sort( ByRef $array, $left, $right )
    $i = $left
    $j = $right
    $v = $array[Round( ( $left + $right ) / 2 ,0)]
    While ( $j > $i )
        While ($array[$i] < $v )
            $i = $i + 1
        WEnd
        While ( $array[$j] > $v )
            $j = $j - 1
        WEnd
        If ( NOT ($i > $j) ) then
            swap($array[$i], $array[$j])
            $i = $i + 1
            $j = $j - 1
        EndIf
    WEnd
    if ( $left  < $j ) then sort( $array, $left, $j  )
    if ( $right > $i ) then sort( $array, $i, $right )
  EndFunc

C[edit]

The implementation in the core implementations section is limited to arrays of integers. The following implementation works with any data type, given its size and a function that compares it. This is similar to what ISO/POSIX compliant C standard libraries provide:

#include <stdlib.h>
#include <stdio.h>
 
static void swap(void *x, void *y, size_t l) {
   char *a = x, *b = y, c;
   while(l--) {
      c = *a;
      *a++ = *b;
      *b++ = c;
   }
}
 
static void sort(char *array, size_t size, int (*cmp)(void*,void*), int begin, int end) {
   if (end > begin) {
      void *pivot = array + begin;
      int l = begin + size;
      int r = end;
      while(l < r) {
         if (cmp(array+l,pivot) <= 0) {
            l += size;
         } else {
            r -= size;
            swap(array+l, array+r, size);
         }
      }
      l -= size;
      swap(array+begin, array+l, size);
      sort(array, size, cmp, begin, l);
      sort(array, size, cmp, r, end);
   }
}
 
void qsort(void *array, size_t nitems, size_t size, int (*cmp)(void*,void*)) {
   sort(array, size, cmp, 0, (nitems-1)*size);
}
 
typedef int type;
 
int type_cmp(void *a, void *b){ return (*(type*)a)-(*(type*)b); }
 
int main(void){ /* simple test case for type=int */
  int num_list[]={5,4,3,2,1};
  int len=sizeof(num_list)/sizeof(type);
  char *sep="";
  int i;
  qsort(num_list,len,sizeof(type),type_cmp);
  printf("sorted_num_list={");
  for(i=0; i<len; i++){
    printf("%s%d",sep,num_list[i]);
    sep=", ";
  }
  printf("};\n");
  return 0;
}

Result:

sorted_num_list={2, 3, 4, 5, 1};  // why?

Here's yet another version with various other improvements:

/*****   macros create functional code   *****/
#define pivot_index() (begin+(end-begin)/2)
#define swap(a,b,t) ((t)=(a),(a)=(b),(b)=(t))
 
void sort(int array[], int begin, int end) {
   /*** Use of static here will reduce memory footprint, but will make it thread-unsafe ***/
   static int pivot;
   static int t;     /* temporary variable for swap */
   if (end > begin) {
      int l = begin + 1;
      int r = end;
      swap(array[begin], array[pivot_index()], t); /*** choose arbitrary pivot ***/
      pivot = array[begin];
      while(l < r) {
         if (array[l] <= pivot) {
            l++;
         } else {
            while(l < --r && array[r] >= pivot) /*** skip superfluous swaps ***/
               ;
            swap(array[l], array[r], t); 
         }
      }
      l--;
      swap(array[begin], array[l], t);
      sort(array, begin, l);
      sort(array, r, end);
   }
}
 
#undef swap
#undef pivot_index

An alternate simple C quicksort. The first C implementation above does not sort the list properly if the initial input is a reverse sorted list, or any time in which the pivot turns out be the largest element in the list. Here is another sample quick sort implementation that does address these issues. Note that the swaps are done inline in this implementation. They may be replaced with a swap function as in the above examples.

void quick(int array[], int start, int end){
    if(start < end){
        int l=start+1, r=end, p = array[start];
        while(l<r){
            if(array[l] <= p)
                l++;
            else if(array[r] >= p)
                r--;
            else
                swap(array[l],array[r]);
        }
        if(array[l] < p){
            swap(array[l],array[start]);
            l--;
        }
        else{
            l--;
            swap(array[l],array[start]);
        }
        quick(array, start, l);
        quick(array, r, end);
    }
}

This sorts an array of integers using quicksort with in-place partition.

 void quicksort(int x[], int first, int last) {
     int pivIndex = 0;
     if(first < last) {
         pivIndex = partition(x,first, last);
         quicksort(x,first,(pivIndex-1));
         quicksort(x,(pivIndex+1),last);
     }
 }
 
 int partition(int y[], int f, int l) {
     int up,down,temp;
     int piv = y[f];
     up = f;
     down = l;
     goto partLS;
     do { 
         temp = y[up];
         y[up] = y[down];
         y[down] = temp;
     partLS:
         while (y[up] <= piv && up < l) {
             up++;
         }
         while (y[down] > piv  && down > f ) {
             down--;
         }
     } while (down > up);
     y[f] = y[down];
     y[down] = piv;
     return down;
 }

The following sample of C code can be compiled to sort a vector of strings (defined as char *list[ ]), integers, doubles, etc. This piece of code implements a mixed iterative-recursive strategy that avoids out of stack risks even in worst case. It runs faster than the standard C lib function qsort(), especially when used with partially sorted arrays (compiled with free Borland bcc32 and tested with 1 million strings vector).

/********** QuickSort(): sorts the vector 'list[]' **********/
 
/**** Compile QuickSort for strings ****/
#define QS_TYPE char*
#define QS_COMPARE(a,b) (strcmp((a),(b)))
 
/**** Compile QuickSort for integers ****/
//#define QS_TYPE int
//#define QS_COMPARE(a,b) ((a)-(b))
 
/**** Compile QuickSort for doubles, sort list in inverted order ****/
//#define QS_TYPE double
//#define QS_COMPARE(a,b) ((b)-(a))
 
void QuickSort(QS_TYPE list[], int beg, int end)
{
    QS_TYPE piv; QS_TYPE tmp;
 
    int  l,r,p;
 
    while (beg<end)    // This while loop will avoid the second recursive call
    {
        l = beg; p = beg + (end-beg)/2; r = end;
 
        piv = list[p];
 
        while (1)
        {
            while ( (l<=r) && ( QS_COMPARE(list[l],piv) <= 0 ) ) l++;
            while ( (l<=r) && ( QS_COMPARE(list[r],piv)  > 0 ) ) r--;
 
            if (l>r) break;
 
            tmp=list[l]; list[l]=list[r]; list[r]=tmp;
 
            if (p==r) p=l;
 
            l++; r--;
        }
 
        list[p]=list[r]; list[r]=piv;
        r--;
 
        // Recursion on the shorter side & loop (with new indexes) on the longer
        if ((r-beg)<(end-l))   
        {
            QuickSort(list, beg, r);
            beg=l;
        }
        else
        {
            QuickSort(list, l, end);
            end=r;
        }
    }   
}

Iterative Quicksort[edit]

Quicksort could also be implemented iteratively with the help of a little stack. Here a simple version with random selection of the pivot element:

typedef long type;                                         /* array type */
#define MAX 64            /* stack size for max 2^(64/2) array elements  */
 
void quicksort_iterative(type array[], unsigned len) {
   unsigned left = 0, stack[MAX], pos = 0, seed = rand();
   for ( ; ; ) {                                           /* outer loop */
      for (; left+1 < len; len++) {                /* sort left to len-1 */
         if (pos == MAX) len = stack[pos = 0];  /* stack overflow, reset */
         type pivot = array[left+seed%(len-left)];  /* pick random pivot */
         seed = seed*69069+1;                /* next pseudorandom number */
         stack[pos++] = len;                    /* sort right part later */
         for (unsigned right = left-1; ; ) { /* inner loop: partitioning */
            while (array[++right] < pivot);  /* look for greater element */
            while (pivot < array[--len]);    /* look for smaller element */
            if (right >= len) break;           /* partition point found? */
            type temp = array[right];
            array[right] = array[len];                  /* the only swap */
            array[len] = temp;
         }                            /* partitioned, continue left part */
      }
      if (pos == 0) break;                               /* stack empty? */
      left = len;                             /* left to right is sorted */
      len = stack[--pos];                      /* get next range to sort */
   } 
}

The pseudorandom selection of the pivot element ensures efficient sorting in O(n log n) under all input conditions (increasing, decreasing order, equal elements). The size of the needed stack is smaller than 2·log₂(n) entries (about 99.9% probability). If a limited stack overflows the sorting simply restarts.

C++[edit]

This is a generic, STL-based version of quicksort.

#include <functional>
#include <algorithm>
#include <iterator>
 
template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
    if( first != last ) {
        BidirectionalIterator left  = first;
        BidirectionalIterator right = last;
        BidirectionalIterator pivot = left++;
 
        while( left != right ) {
            if( cmp( *left, *pivot ) ) {
                ++left;
            } else {
                while( (left != right) && cmp( *pivot, *right ) )
                    --right;
                std::iter_swap( left, right );
            }
        }
 
        --left;
        std::iter_swap( pivot, left );
 
        quick_sort( first, left, cmp );
        quick_sort( right, last, cmp );
    }
}
 
template< typename BidirectionalIterator >
    inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
        quick_sort( first, last,
                std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
                );
    }

Here's a shorter version than the one in the core implementations section which takes advantage of the standard library's partition() function:

#include <algorithm>
#include <iterator>
#include <functional>
 
using namespace std;
 
template <typename T>
void sort(T begin, T end) {
    if (begin != end) {
        T middle = partition (begin, end, bind2nd(
                    less<typename iterator_traits<T>::value_type>(), *begin));
        sort (begin, middle);
//        sort (max(begin + 1, middle), end);
        T new_middle = begin;
        sort (++new_middle, end);
    }
}

C#[edit]

The following C# implementation uses a random pivot.

static class Quicksort
{
    private static void Swap<T>(T[] array, int left, int right)
    {
        var temp = array[right];
        array[right] = array[left];
        array[left] = temp;
    }
 
    public static void Sort<T>(T[] array, IComparer<T> comparer = null)
    {
        Sort(array, 0, array.Length - 1, comparer);
    }
 
    public static void Sort<T>(T[] array, int startIndex, int endIndex, IComparer<T> comparer = null)
    {
        if (comparer == null)
            comparer = Comparer<T>.Default;
 
        int left = startIndex;
        int right = endIndex;
        int pivot = startIndex;
        startIndex++;
 
        while (endIndex >= startIndex)
        {
            if (comparer.Compare(array[startIndex], array[pivot]) >= 0 && comparer.Compare(array[endIndex], array[pivot]) < 0)
                Swap(array, startIndex, endIndex);
            else if (comparer.Compare(array[startIndex], array[pivot]) >= 0)
                endIndex--;
            else if (comparer.Compare(array[endIndex], array[pivot]) < 0)
                startIndex++;
            else
            {
                endIndex--;
                startIndex++;
            }
        }
 
        Swap(array, pivot, endIndex);
        pivot = endIndex;
        if (pivot > left)
            Sort(array, left, pivot);
        if (right > pivot + 1)
            Sort(array, pivot + 1, right);
    }
}

Common Lisp[edit]

(defun partition (fun array)
  (list (remove-if-not fun array) (remove-if fun array)))
 
(defun sort (array)
  (if (null array) nil
    (let ((part (partition (lambda (x) (< x (car array))) (cdr array))))
      (append (sort (car part)) (cons (car array) (sort (cadr part)))))))

D[edit]

Based on the C code posted at rossetacode.org

void sort(T)(T arr) {
    if (arr.length > 1) {
        quickSort(arr.ptr, arr.ptr + (arr.length - 1));
    }
}
 
void quickSort(T)(T *left, T *right) {
    if (right > left) {
        T pivot = left[(right - left) / 2];
        T* r = right, l = left;
        do {
            while (*l < pivot) l++;
            while (*r > pivot) r--;
            if (l <= r) swap(*l++, *r--);
        } while (l <= r);
        quickSort(left, r);
        quickSort(l, right);
    }
}

Delphi[edit]

This example sorts strings using quicksort.

Note: This can be considered bad code, as it is very slow.

procedure QuickSort(const AList: TStrings; const AStart, AEnd: Integer);
  procedure Swap(const AIdx1, AIdx2: Integer);
  var
    Tmp: string;
  begin
    Tmp := AList[AIdx1];
    AList[AIdx1] := AList[AIdx2];
    AList[AIdx2] := Tmp;
  end;
 
var
  Left: Integer;
  Pivot: string;
  Right: Integer;
begin
  if AStart >= AEnd then
    Exit;
  Pivot := AList[AStart];
  Left := AStart + 1;
  Right := AEnd;
  while Left < Right do
    begin
      if AList[Left] < Pivot then
        Inc(Left)
      else
        begin
          Swap(Left, Right);
          Dec(Right);
        end;
    end;
  Dec(Left);
  Swap(Left, AStart);
  Dec(Left);
  QuickSort(AList, AStart, Left);
  QuickSort(AList, Right, AEnd);
end;

This implementation sorts an array of integers.

procedure QSort(var A: array of Integer);
  procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
  var Lo, Hi, Mid, T: Integer;
  begin
    Lo := iLo;
    Hi := iHi;
    Mid := A[(Lo + Hi) div 2];
    repeat
      while A[Lo] < Mid do
        Inc(Lo);
      while A[Hi] > Mid do
        Dec(Hi);
      if Lo <= Hi then begin
        T := A[Lo];
        A[Lo] := A[Hi];
        A[Hi] := T;
        Inc(Lo);
        Dec(Hi);
      end;
    until Lo > Hi;
    if Hi > iLo then
      QuickSort(A, iLo, Hi);
    if Lo < iHi then
      QuickSort(A, Lo, iHi);
  end;
begin
  QuickSort(A, Low(A), High(A));
end;

This slightly modified implementation sorts an array of records. This is approximately 8x quicker than the previous one. Note: this is QuickSort only, more speedup can be gain with handling trivial case (comparing two values), or implementing Bubble or Shell sort on small ranges.

type
  TCustomRecord = record
    Key: WideString;
    foo1:Int64;
    foo2:TDatetime;
    foo3:Extended;
  end;
  TCustomArray = array of TCustomRecord;
 
procedure QuickSort(var A: TCustomArray; L, R: Integer; var tmp: TCustomRecord);
var
  OrigL,
  OrigR: Integer;
  Pivot: WideString;
  GoodPivot,
  SortPartitions: Boolean;
begin
  if L<R then begin
    Pivot:=A[L+Random(R-L)].Key;
    OrigL:=L; //saving original bounds
    OrigR:=R;
    repeat
      L:=OrigL; //restoring original bounds if we
      R:=OrigR; //have chosen a bad pivot value
      while L<R do begin
        while (L<R) and (A[L].Key<Pivot) do Inc(L);
        while (L<R) and (A[R].Key>=Pivot) do Dec(R);
        if (L<R) then begin
          tmp:=A[L];
          A[L]:=A[R];
          A[R]:=tmp;
          Dec(R);
          Inc(L);
        end;
      end;
      if A[L].Key>=Pivot then Dec(L);                            //has we managed to choose
      GoodPivot:=L>=OrigL;                                       //a good pivot value?
      SortPartitions:=True;                                      //if so, then sort on
      if not GoodPivot then begin                                //bad luck, the pivot is the smallest one in our range
        GoodPivot:=True;                                         //let's presume that all the values are equal to pivot
        SortPartitions:=False;                                   //then no need to sort it
        for R := OrigL to OrigR do if A[R].Key<>Pivot then begin //we have at least one different value than our pivot
          Pivot:=A[R].Key;                                       //so this will be our new pivot
          GoodPivot:=False;                                      //we have to start again sorting this range
          Break;
        end;
      end;
    until GoodPivot;
    if SortPartitions then begin
      QuickSort(A, OrigL, L, tmp);
      QuickSort(A, L+1, OrigR, tmp);
    end;
  end;
end;

Erlang[edit]

The following Erlang code sorts lists of items of any type.

qsort([]) -> [];
qsort([Pivot|Rest]) ->
    qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).

F#[edit]

let rec quicksort l =
    match l with
    | [] -> []
    | h::t -> quicksort (List.filter (fun x -> x < h) t) @ h :: quicksort (List.filter (fun x -> x >= h) t)

Groovy[edit]

static def quicksort(v) {
   if (!v || v.size <= 1) return v
   def (less, more) = v[1..-1].split { it <= v[0] }
   quicksort(less) + v[0] + quicksort(more)
}

Haskell[edit]

The Haskell code in the core implementations section is almost self explanatory but can suffer from inefficiencies because it crawls through the list "rest" twice, once for each list comprehension. A smart implementation can perform optimizations to prevent this inefficiency, but these are not required by the language. The following implementation does not have the aforementioned inefficiency, as it uses a partition function that ensures that we only traverse `xs' once:

    import Data.List (partition)
 
    sort:: (Ord a) => [a] -> [a]
    sort [] = []
    sort (x:xs) = sort less ++ [x] ++ sort greatereq
        where (less,greatereq) = partition (< x) xs

Another version:

    quicksort :: Ord a => [a] -> [a]
    quicksort []           = []
    quicksort (pivot:tail) = quicksort less ++ [pivot] ++ quicksort greater
        where less    = [y | y <- tail, y < pivot]
              greater = [y | y <- tail, y >= pivot]

An even shorter version:

    qsort []     = []
    qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

A rather fast version which builds the list from the end, making the use of (++) ok, it only traverses the list of lower parts, prepending them to head of the higher and equal lists. One draw back is that it requires the whole list be sorted, it's not very good for laziness:

    qsort xs = qsort' xs []
    
    qsort' [] end = end
    qsort' (x:xs) end = qsort' lower (equal ++ qsort' higher end)
        where (lower, equal, higher) = partit x xs ([],[x],[])
    
    partit s [] part = part
    partit s (x:xs) (l,e,h) 
        |x < s = partit s xs (x:l, e, h)
        |x > s = partit s xs (l, e, x:h)
        |otherwise = partit s xs (l, x:e, h)

J[edit]

The J example in the core implementations section is extremely terse and difficult to understand. This implementation, from the J Dictionary, is less obtuse:

sel=: adverb def 'x. # ['

quicksort=: verb define
 if. 1 >: #y. do. y.
 else. 
  (quicksort y. <sel e),(y. =sel e),quicksort y. >sel e=.y.{~?#y.
 end.
)

Java[edit]

Here is a sample Java implementation that sorts an ArrayList of numbers.

import java.util.ArrayList;
import java.util.Random;
 
public class QuickSort {
 
    public static final int NUMBERS_TO_SORT = 25;
 
    public QuickSort() {
    }
 
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        Random rand = new Random();
        for (int i = 0; i < NUMBERS_TO_SORT; i++)
            numbers.add(rand.nextInt(NUMBERS_TO_SORT + 1));
        for (int number : numbers)
            System.out.print(number + " ");
        System.out.println("\nBefore quick sort\n\n");
        for (int number : quicksort(numbers))
            System.out.print(number + " ");
        System.out.println("\nAfter quick sort\n\n");
    }
 
    public static ArrayList<Integer> quicksort(ArrayList<Integer> numbers) {
        if (numbers.size() <= 1)
            return numbers;
        int pivot = numbers.size() / 2;
        ArrayList<Integer> lesser = new ArrayList<Integer>();
        ArrayList<Integer> greater = new ArrayList<Integer>();
        int sameAsPivot = 0;
        for (int number : numbers) {
            if (number > numbers.get(pivot))
                greater.add(number);
            else if (number < numbers.get(pivot))
                lesser.add(number);
            else
                sameAsPivot++;
        }
        lesser = quicksort(lesser);
        for (int i = 0; i < sameAsPivot; i++)
            lesser.add(numbers.get(pivot));
        greater = quicksort(greater);
        ArrayList<Integer> sorted = new ArrayList<Integer>();
        for (int number : lesser)
            sorted.add(number);
        for (int number: greater)
            sorted.add(number);
        return sorted;
    }
}

The following Java implementation uses a randomly selected pivot. Analogously to the Erlang solution above, a user-supplied Template:Javadoc:SE determines the partial ordering of array elements:

import java.util.Comparator;
import java.util.Random;
 
public class Quicksort {
    public static final Random RND = new Random(); 
    private static void swap(Object[] array, int i, int j) {
        Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    private static <E> int partition(E[] array, int begin, int end, Comparator<? super E>  cmp) {
        int index = begin + RND.nextInt(end - begin + 1);
        E pivot = array[index];
        swap(array, index, end); 
        for (int i = index = begin; i < end; ++ i) {
            if (cmp.compare(array[i], pivot) <= 0) {
                swap(array, index++, i);
            }
        }
        swap(array, index, end); 
        return (index);
    }
    private static <E> void qsort(E[] array, int begin, int end, Comparator<? super E> cmp) {
        if (end > begin) {
            int index = partition(array, begin, end, cmp);
            qsort(array, begin, index - 1, cmp);
            qsort(array, index + 1,  end,  cmp);
        }
    }
    public static <E> void sort(E[] array, Comparator<? super E>  cmp) {
        qsort(array, 0, array.length - 1, cmp);
    }
}

With the advent of J2SE 5.0 you can use parameterized types to avoid passing the Comparator used above.

import java.util.Arrays;
import java.util.Random;
 
public class QuickSort {
    public static final Random RND = new Random();
 
    private static void swap(Object[] array, int i, int j) {
        Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
 
    private static <E extends Comparable<? super E>> int partition(E[] array, int begin, int end) {
        int index = begin + RND.nextInt(end - begin + 1);
        E pivot = array[index];
        swap(array, index, end);
        for (int i = index = begin; i < end; ++i) {
            if (array[i].compareTo(pivot) <= 0) {
                swap(array, index++, i);
            }
        }
        swap(array, index, end);
        return (index);
    }
 
    private static <E extends Comparable<? super E>> int void qsort(E[] array, int begin, int end) {
        if (end > begin) {
            int index = partition(array, begin, end);
            qsort(array, begin, index - 1);
            qsort(array, index + 1, end);
        }
    }
 
    public static <E extends Comparable<? super E>> int void sort(E[] array) {
        qsort(array, 0, array.length - 1);
    }
 
    // Example uses
    public static void main(String[] args) {
        Integer[] l1 = { 5, 1024, 1, 88, 0, 1024 };
        System.out.println("l1  start:" + Arrays.toString(l1));
        QuickSort.sort(l1);
        System.out.println("l1 sorted:" + Arrays.toString(l1));
 
        String[] l2 = { "gamma", "beta", "alpha", "zoolander" };
        System.out.println("l2  start:" + Arrays.toString(l2));
        QuickSort.sort(l2);
        System.out.println("l2 sorted:" + Arrays.toString(l2));
    }
}

Another implementation.

import java.util.*;
public class QuickSort
{
    public static void main(String[] args) 
    {
        /* Data to be sorted */
        List<Integer> data = createRandomData();
 
        /* Generate a random permutation of the data.
         * This sometimes improves the performance of QuickSort
         */
        Collections.shuffle(data);
 
        /* Call quick sort */
        List<Integer> sorted = quickSort(data);
 
        /* Print sorted data to the standard output */
        System.out.println(sorted);
    }
 
    private static final Random rand = new Random();
 
    /* Add data to be sorted to the list */
    public static List<Integer> createRandomData()
    {
        int max = 1000000;
        int len = 1000;
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0; i<len; i++)
        {
            /* You can add any type that implements
             * the Comparable interface */             
            list.add(Integer.valueOf(rand.nextInt(max)));
        }
        return list;
    }
 
    public static <E extends Comparable<? super E>> List<E> quickSort(List<E> data)
    {
        List<E> sorted = new ArrayList<E>();
        rQuickSort(data, sorted);
        return sorted;
    }
 
    /**
     * A recursive implementation of QuickSort. Pivot selection
     * is random. The algorithm is stable.
     */
    public static <E extends Comparable<? super E>> void rQuickSort(List<E> data, List<E> sorted)
    {   
        if(data.size() == 1)
        {
            sorted.add(data.iterator().next());
            return;
        }
 
        if(data.size() == 0)
        {
            return;
        }
 
        /* choose the pivot randomly */
        int pivot = rand.nextInt(data.size());
        E pivotI = data.get(pivot);
        List<E> fatPivot = new ArrayList<E>();
        List<E> left = new ArrayList<E>();
        List<E> right = new ArrayList<E>();
 
        /* partition data */
        for(E next : data)
        {
            int compare = pivotI.compareTo(next);
            if(compare < 0)
            {
                right.add(next);
            }
            else if(compare > 0)
            {
                left.add(next);
            }
            else
            {
                fatPivot.add(next);
            }
        }
        rQuickSort(left, sorted);
        sorted.addAll(fatPivot);
        rQuickSort(right, sorted);
    }
}

Here is a sample that uses recursion, like the Groovy implementation:

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
 
public class Quicksort {
 
        @SuppressWarnings("unchecked")
        public static <E extends Comparable<? super E>> List<E>[] split(List<E> v) {
                List<E>[] results = (List<E>[])new List[] { new LinkedList<E>(), new LinkedList<E>() };
                Iterator<E> it = v.iterator();
                E pivot = it.next();
                while (it.hasNext()) {
                        E x = it.next();
                        if (x.compareTo(pivot) < 0) results[0].add(x);
                        else results[1].add(x);
                }
                return results;
        }
 
        public static <E extends Comparable<? super E>> List<E> quicksort(List<E> v) {
                if (v == null || v.size() <= 1) return v;
                final List<E> result = new LinkedList<E>();
                final List<E>[] lists = split(v);
                result.addAll(quicksort(lists[0]));
                result.add(v.get(0));
                result.addAll(quicksort(lists[1]));
                return result;
        }
 
}

JavaScript[edit]

function qsort(a) {
    if (a.length == 0) return [];
 
    var left = [], right = [], pivot = a[0];
 
    for (var i = 1; i < a.length; i++) {
        a[i] < pivot ? left.push(a[i]) : right.push(a[i]);
    }
 
    return qsort(left).concat(pivot, qsort(right));
}

Mathematica[edit]

Here's a functional-style implementation:

QSort[{}] := {}
QSort[{h_, t___}] :=
  Join[QSort[Select[{t}, # < h &]], {h}, QSort[Select[{t}, # >= h &]]]

Here's a test driver which should yield True:

OrderedQ[QSort[Table[Random[Integer, {1, 10000}], {i, 1, 10000}]]]

MATLAB[edit]

function [y]=quicksort(x)
% Uses quicksort to sort an array. Two dimensional arrays are sorted column-wise.
[n,m]=size(x);
if(m>1)
    y=x;
    for j=1:m
        y(:,j)=quicksort(x(:,j));
    end
    return;
end
% The trivial cases
if(n<=1);y=x;return;end;
    if(n==2)
        if(x(1)>x(2))
            x=[x(2); x(1)];
        end
        y=x;
    return;
    end
% The non-trivial case
% Find a pivot, and divide the array into two parts.
% All elements of the first part are less than the
% pivot, and the elements of the other part are greater 
% than or equal to the pivot.
m=fix(n/2);
pivot=x(m);
ltIndices=find(x<pivot); % Indices of all elements less than pivot.
if(isempty(ltIndices)) % This happens when pivot is miniumum of all elements.
    ind=find(x>pivot); % Find the indices of elements greater than pivot.
    if(isempty(ind));y= x;return;end; % This happens when all elements are the same.
        pivot=x(ind(1)); % Use new pivot.
        ltIndices=find(x<pivot);
end
% Now find the indices of all elements not less than pivot.
% Since the pivot is an element of the array, 
% geIndices cannot be empty.
geIndices=find(x>=pivot);
% Recursively sort the two parts of the array and concatenate 
% the sorted parts.
y= [quicksort(x(ltIndices));quicksort(x(geIndices))];

Miranda[edit]

   sort []           = []  
   sort (pivot:rest) = sort [ y | y <- rest; y <= pivot ]  
                        ++ [pivot] ++
                       sort [ y | y <- rest; y >  pivot ]

ML[edit]

(* quicksort_r recurses down the list partitioning it into elements smaller than the pivot and others.
    it then combines the lists at the end with the pivot in the middle.

   It can be generalised to take a comparison function and thus remove the "int" type restriction.
   It could also be generalised to use a Cons() function instead of the :: abbreviation allowing for 
   other sorts of lists.
 *)

fun quicksort [] = []
|   quicksort (p::lst) = 
      let fun quicksort_r pivot ([], front, back) =  (quicksort front) @ [pivot] @ (quicksort back)
          |   quicksort_r pivot (x::xs, front, back) = 
                if x < pivot then 
                   quicksort_r pivot (xs, x::front, back)
                else 
                   quicksort_r pivot (xs, front, x::back)
      in
         quicksort_r p (lst, [], [])
      end
;
(* val quicksort = fn : int list -> int list *)

OCaml[edit]

let rec sort = function
      [] -> []
    | pivot :: rest ->
        let left, right = List.partition (( > ) pivot) rest in
        sort left @ pivot :: sort right

Perl[edit]

sub qsort {
  return () unless @_;
  (qsort(grep { $_ < $_[0] } @_[1..$#_]), $_[0],
   qsort(grep { $_ >= $_[0] } @_[1..$#_]));
}

Or:

sub qsort {
  @_ or return ();
  my $p = shift;
  (qsort(grep $_ < $p, @_), $p, qsort(grep $_ >= $p, @_));
}

Perl 6[edit]

multi quicksort () { () }
multi quicksort (*$x, *@xs) {
   my @pre  = @xs.grep:{ $_ <  $x };
   my @post = @xs.grep:{ $_ >= $x };
   (@pre.quicksort, $x, @post.quicksort);
}

PHP[edit]

function quicksort($array) {
    if(count($array) < 2) return $array;
 
    $left = $right = array();
 
    reset($array);
    $pivot_key = key($array);
    $pivot = array_shift($array);
 
    foreach($array as $k => $v) {
        if($v < $pivot)
            $left[$k] = $v;
        else
            $right[$k] = $v;
    }
 
    return array_merge(quicksort($left), array($pivot_key => $pivot), quicksort($right));
}

With array_filter and consecutive numerical keys

function quicksort($array) {
  if (count($array) <= 1) {
    return $array;
  }
 
  $pivot_value = array_shift($array);
 
  return array_merge(
    quicksort(array_filter($array, function ($v) use($pivot_value) {return $v < $pivot_value;})),
    array($pivot_value),
    quicksort($higher = array_filter($array, function ($v) use($pivot_value) {return $v >= $pivot_value;}))
  );
}

Prolog[edit]

The version in the core implementations section is concise and, because it uses tail recursion, efficient. Here's another version:

partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
    (   X @< Pivot ->
        Smalls = [X|Rest],
        partition(Xs, Pivot, Rest, Bigs)
    ;   Bigs = [X|Rest],
        partition(Xs, Pivot, Smalls, Rest)
    ).
 
quicksort([])     --> [].
quicksort([X|Xs]) --> 
    { partition(Xs, X, Smaller, Bigger) },
    quicksort(Smaller), [X], quicksort(Bigger).

Python[edit]

Using list comprehensions:

 def qsort(L):
   if L == []: return []
   return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + \
          qsort([x for x in L[1:] if x>=L[0]])

With in place partitioning and random pivot selection:

import random
 
def _doquicksort(values, left, right):
    """Quick sort"""
    def partition(values, left, right, pivotidx):
        """In place paritioning from left to right using the element at
        pivotidx as the pivot. Returns the new pivot position."""
 
        pivot = values[pivotidx]
        # swap pivot and the last element
        values[right], values[pivotidx] = values[pivotidx], values[right]
 
        storeidx = left
        for idx in range(left, right):
            if values[idx] < pivot:
                values[idx], values[storeidx] = values[storeidx], values[idx]
                storeidx += 1
 
        # move pivot to the proper place
        values[storeidx], values[right] = values[right], values[storeidx]
        return storeidx
 
    if right > left:
        # random pivot
        pivotidx = random.randint(left, right)
        pivotidx = partition(values, left, right, pivotidx)
        _doquicksort(values, left, pivotidx)
        _doquicksort(values, pivotidx + 1, right)
 
    return values
 
def quicksort(mylist):
    return _doquicksort(mylist, 0, len(mylist) - 1)

Ruby[edit]

class QuickSort
 
  def self.sort!(keys)
    quick(keys,0,keys.size-1)
  end
 
  private
 
  def self.quick(keys, left, right)
    if left < right
      pivot = partition(keys, left, right)
      quick(keys, left, pivot-1)
      quick(keys, pivot+1, right)
    end
    keys
  end
 
  def self.partition(keys, left, right)
    x = keys[right]
    i = left-1
    for j in left..right-1
      if keys[j] <= x
        i += 1
        keys[i], keys[j] = keys[j], keys[i]
      end
    end
    keys[i+1], keys[right] = keys[right], keys[i+1]
    i+1
  end
 
end

Using Closures:

def quicksort(list)
   return list if list.length <= 1
   pivot = list.shift
   left, right = list.partition { |el| el < pivot }
   quicksort(left) + [pivot] + quicksort(right)
end

Scala[edit]

def qsort(l: List[Int]): List[Int] = {
    l match {
        case List() => l
        case _ =>  qsort(for(x <- l.tail if x < l.head) yield x) ::: List(l.head) ::: qsort(for(x <-1.tail if x >= l.head) yield x)
    }
}

Or shorter version:

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

Scheme[edit]

This uses SRFI 1 and SRFI 8. It avoids redundantly traversing the list: it partitions it with the pivot in one traversal, not two, and it avoids copying entire lists to append them, by instead only adding elements on the front of the output list's tail.

(define (quicksort list elt<)
  (let qsort ((list list) (tail '()))
    (if (null-list? list)
        tail
        (let ((pivot (car list)))
          (receive (smaller larger)
                   (partition (lambda (x) (elt< x pivot))
                              (cdr list))
            (qsort smaller (cons pivot (qsort larger tail))))))))

Shen[edit]

(define filter
  {(A --> boolean) --> (list A) --> (list A)}
  _   []      -> []
  T?  [A | B]  -> (append [A] (filter T? B)) where (T? A)
  T?  [_|B]    -> (filter T? B)
)
 
(define q-sort
  {(list number) --> (list number)}
  [] -> []
  [A | B] -> (append (q-sort (filter (> A) [A|B]))
                     [A]
                     (q-sort (filter (< A) [A|B]))))

Shell[edit]

While many of the other scripting languages (e.g. Perl, Python, Ruby) have a built-in library sort routine, POSIX shells generally do not.

The following was adapted from the Applescript code above and used in the bash debugger [1]. It has been tested on bash, zsh, and the Korn shell (ksh).

# Sort global array, $list, starting from $1 to up to $2. 0 is 
# returned if everything went okay, and nonzero if there was an error.
 
# We use the recursive quicksort of Tony Hoare with inline array
# swapping to partition the array. The partition item is the middle
# array item. String comparison is used.  The sort is not stable.
 
# It is necessary to use "function" keyword in order not to inherit 
# variables being defined via typset, which solves the instability 
# problem here.This is specified in the manual page of ksh.
 
function sort_list() {
  (($# != 2)) && return 1
  typeset -i left=$1
  ((left < 0)) || (( 0 == ${#list[@]})) && return 2
  typeset -i right=$2
  ((right >= ${#list[@]})) && return 3
  typeset -i i=$left; typeset -i j=$right
  typeset -i mid; ((mid= (left+right) / 2))
  typeset partition_item; partition_item="${list[$mid]}"
  typeset temp
  while ((j > i)) ; do
      while [[ "${list[$i]}" < "$partition_item" ]] ; do
          ((i++))
      done
      while [[ "${list[$j]}" > "$partition_item" ]] ; do
          ((j--))
      done
      if ((i <= j)) ; then
          temp="${list[$i]}"; list[$i]="${list[$j]}"; list[$j]="$temp"
          ((i++))
          ((j--))
      fi
  done
  ((left < j))  && sort_list $left  $j  
  ((right > i)) && sort_list $i $right
  return $?
}
 
if [[ $0 == *sort.sh ]] ; then 
    [[ -n $ZSH_VERSION ]] && setopt ksharrays
    typeset -a list
    list=()
    sort_list -1 0 
    typeset -p list
    list=('one')
    typeset -p list
    sort_list 0 0 
    typeset -p list
    list=('one' 'two' 'three')
    sort_list 0 2
    typeset -p list
    list=(4 3 2 1)
    sort_list 0 3
    typeset -p list
fi

Standard ML[edit]

The following example—though less general than the snippet in the core implementations section in that it does not accept a predicate argument—strives to more closely resemble the implementations in the other functional languages. The use of List.partition in both examples enables the implementation to walk the list only once per call, thereby reducing the constant factor of the algorithm.

fun qsort [] = []
  | qsort (h::t) = let val (left, right) = List.partition (fn x => x < h) t
                   in qsort left @ h :: qsort right
                   end;

Replacing the predicate is trivial:

fun qsort pred [] = []
  | qsort pred (h::t) = let val (left, right) = List.partition (fn x => pred (x, h)) t
                        in qsort pred left @ h :: qsort pred right
                        end;

A cleaner version that sacrifices the efficiency of List.partition and resembles the list-comprehension versions in other functional languages:

fun qsort [] = []
  | qsort (h::t) = qsort (List.filter (fn x => x < h) t) @ h :: qsort (List.filter (fn x => x >= h) t);

Visual Basic[edit]

Option Explicit
 
' a position, which is *hopefully* never used:
Public Const N_POS = -2147483648#
 
Public Sub Swap(ByRef Data() As Variant, _
                Index1 As Long, _
                Index2 As Long)
    If Index1 <> Index2 Then
        Dim tmp As Variant
 
        If IsObject(Data(Index1)) Then
            Set tmp = Data(Index1)
        Else
            tmp = Data(Index1)
        End If
 
        If IsObject(Data(Index2)) Then
            Set Data(Index1) = Data(Index2)
        Else
            Data(Index1) = Data(Index2)
        End If
 
        If IsObject(tmp) Then
            Set Data(Index2) = tmp
        Else
            Data(Index2) = tmp
        End If
 
        Set tmp = Nothing
    End If
End Sub
 
Public Sub QuickSort(ByRef Data() As Variant, _
                     Optional ByVal Lower As Long = N_POS, _
                     Optional ByVal Upper As Long = N_POS)
    If Lower = N_POS Then
        Lower = LBound(Data)
    End If
 
    If Upper = N_POS Then
        Upper = UBound(Data)
    End If
 
    If Lower < Upper Then
        Dim Right As Long
        Dim Left  As Long
 
        Left = Lower + 1
        Right = Upper + 1
 
        Do While Left < Right
            If Data(Left) <= Data(Lower) Then
                Left = Left + 1
            Else
                Right = Right - 1
                Swap Data, Left, Right
            End If
        Loop
 
        Left = Left - 1
        Swap Data, Lower, Left
        QuickSort Data, Lower, Left - 1
        QuickSort Data, Right, Upper
    End If
End Sub

Another implementation:

Function Quicksort(ByRef aData() As Long) As Long()
    Dim lPivot As Long
 
    Dim aLesser() As Long
    Dim aPivotList() As Long
    Dim aBigger() As Long
    Dim i As Long
    Dim count As Long
    Dim ret() As Long
 
    On Error Resume Next
 
    count = UBound(aData)
 
    If Err Then
        Exit Function
    ElseIf count = 0 Then
        Quicksort = aData
        Exit Function
    End If
 
    On Error GoTo 0
 
    Randomize
    lPivot = aData(Int(Rnd * count))
 
    For i = 0 To count
        If aData(i) < lPivot Then AddTo aData(i), aLesser
        If aData(i) = lPivot Then AddTo aData(i), aPivotList
        If aData(i) > lPivot Then AddTo aData(i), aBigger
    Next
 
    aLesser = Quicksort(aLesser)
    aPivotList = aPivotList
    aBigger = Quicksort(aBigger)
 
    ret = JoinLists(aLesser, aPivotList, aBigger)
 
    Quicksort = ret
End Function
 
Sub AddTo(ByVal lData As Long, ByRef aWhere() As Long)
    Dim count As Long
 
    On Error Resume Next
 
    count = UBound(aWhere) + 1
    ReDim Preserve aWhere(count)
 
    aWhere(count) = lData
    On Error GoTo 0
End Sub
 
Function JoinLists(ByRef Arr1() As Long, ByRef Arr2() As Long, ByRef Arr3() As Long) As Long()
    Dim count1 As Long
    Dim count2 As Long
    Dim count3 As Long
    Dim i As Long
    Dim ret() As Long
    Dim cnt As Long
 
    On Error Resume Next
 
    Err.Clear
 
    count1 = UBound(Arr1)
    If Err Then count1 = -1
    Err.Clear
 
    count2 = UBound(Arr2)
    If Err Then count2 = -1
    Err.Clear
 
    count3 = UBound(Arr3)
    If Err Then count3 = -1
    Err.Clear
 
    On Error GoTo 0
 
    ReDim ret(count1 + (count2 + 1) + (count3 + 1))
 
    For i = 0 To count1
        ret(i) = Arr1(i)
    Next
 
    For i = count1 + 1 To (count2 + 1) + count1
        ret(i) = Arr2(i - count1 - 1)
    Next
 
    For i = count2 + 1 + count1 + 1 To (count3 + 1) + (count2 + 1) + count1
        ret(i) = Arr3(i - count2 - 1 - count1 - 1)
    Next
 
    JoinLists = ret
End Function

To generalize it, simply change types to Variant.

  <p:declare-step xmlns:p="http://www.w3.org/ns/xproc" xmlns:c="http://www.w3.org/ns/xproc-step" xmlns:ix="http://www.innovimax.fr/ns" version="1.0">
    <p:input port="source">
      <p:inline exclude-inline-prefixes="#all">
        <root>
          <doc>03</doc>
          <doc>04</doc>
          <doc>07</doc>
          <doc>06</doc>
          <doc>02</doc>
          <doc>01</doc>
          <doc>08</doc>
          <doc>10</doc>
          <doc>09</doc>
          <doc>05</doc>
          <doc>03</doc>
          <doc>04</doc>
          <doc>07</doc>
          <doc>06</doc>
          <doc>02</doc>
          <doc>01</doc>
          <doc>08</doc>
          <doc>10</doc>
          <doc>09</doc>
          <doc>05</doc>
          <doc>03</doc>
          <doc>04</doc>
          <doc>07</doc>
          <doc>06</doc>
          <doc>02</doc>
          <doc>01</doc>
          <doc>08</doc>
          <doc>10</doc>
          <doc>09</doc>
          <doc>05</doc>
          <doc>03</doc>
          <doc>04</doc>
          <doc>07</doc>
          <doc>06</doc>
          <doc>02</doc>
          <doc>01</doc>
          <doc>08</doc>
          <doc>10</doc>
          <doc>09</doc>
          <doc>05</doc>
          <doc>03</doc>
          <doc>04</doc>
          <doc>07</doc>
          <doc>06</doc>
          <doc>02</doc>
          <doc>01</doc>
          <doc>08</doc>
          <doc>10</doc>
          <doc>09</doc>
          <doc>05</doc>
          <doc>03</doc>
          <doc>04</doc>
          <doc>07</doc>
          <doc>06</doc>
          <doc>02</doc>
          <doc>01</doc>
          <doc>08</doc>
          <doc>10</doc>
          <doc>09</doc>
          <doc>05</doc>
        </root>
      </p:inline>
    </p:input>
    <p:output port="result"/>
    <p:declare-step type="ix:sort" name="sort">
      <p:documentation>
        <p>XProc QuickSort implementation</p>
        <p>Copyright (C) 2010 Mohamed ZERGAOUI Innovimax</p>
        <p>This program is free software: you can redistribute it and/or modify
          it under the terms of the GNU General Public License as published by
          the Free Software Foundation, either version 3 of the License, or
          (at your option) any later version.</p>
        <p>This program is distributed in the hope that it will be useful,
          but WITHOUT ANY WARRANTY; without even the implied warranty of
          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
          GNU General Public License for more details.</p>
 
        <p>You should have received a copy of the GNU General Public License
          along with this program. If not, see
          http://www.gnu.org/licenses/.</p>
      </p:documentation>
      <p:input port="source" sequence="true"/>
      <p:output port="result" sequence="true"/>
      <p:option name="key" required="true"/>
      <p:count limit="2"/>
      <p:choose>
        <p:when test="number(.) le 1">
          <p:identity>
            <p:input port="source">
              <p:pipe port="source" step="sort"/>
            </p:input>
          </p:identity>
        </p:when>
        <p:otherwise>
          <p:split-sequence test="position() = 1" name="split">
            <p:input port="source">
              <p:pipe port="source" step="sort"/>
            </p:input>
          </p:split-sequence>
          <p:filter name="filter">
            <p:with-option name="select" select="$key">
              <p:empty/>
            </p:with-option>
          </p:filter>
          <p:group>
            <p:variable name="pivot-key" select=".">
              <p:pipe port="result" step="filter"/>
            </p:variable>
            <p:split-sequence name="split-pivot">
              <p:input port="source">
                <p:pipe port="not-matched" step="split"/>
              </p:input>
              <p:with-option name="test" select="concat($key, ' &lt;= ',
                $pivot-key)"/>
            </p:split-sequence>
            <ix:sort name="less">
              <p:with-option name="key" select="$key">
                <p:empty/>
              </p:with-option>
              <p:input port="source">
                <p:pipe port="matched" step="split-pivot"/>
              </p:input>
            </ix:sort>
            <ix:sort name="greater">
              <p:with-option name="key" select="$key">
                <p:empty/>
              </p:with-option>
              <p:input port="source">
                <p:pipe port="not-matched" step="split-pivot"/>
              </p:input>
            </ix:sort>
            <p:identity>
              <p:input port="source">
                <p:pipe port="result" step="less"/>
                <p:pipe port="matched" step="split"/>
                <p:pipe port="result" step="greater"/>
              </p:input>
            </p:identity>
          </p:group>
        </p:otherwise>
      </p:choose>
    </p:declare-step>
    <p:for-each>
      <p:iteration-source select="/root/doc"/>
      <p:identity/>
    </p:for-each>
    <ix:sort key="/doc"/>
    <p:wrap-sequence wrapper="root"/>
  </p:declare-step>

Zilog Z80000 Assembly[edit]

This implementation is in z80 assembly code. The processor is really ancient, and so it's basically a register-stack recursion juggling feat. More on it and the author's comments here. It takes the register pairs BC and HL which point to the start and end memory locations to the list of one-byte elements to be sorted. All registers are filled with "garbage" data in the process, so they need to be pushed to the stack to be saved. The script is about 44 bytes long, and does not have pivot-optimizing code.

;
; Usage: bc->first, de->last,
;        call qsort
; Destroys: abcdefhl
;
qsort   ld      hl,0
        push    hl
qsloop  ld      h,b
        ld      l,c
        or      a
        sbc     hl,de
        jp      c,next1 ;loop until lo<hi
        pop     bc
        ld      a,b
        or      c
        ret     z       ;bottom of stack
        pop     de
        jp      qsloop
next1   push    de      ;save hi,lo
        push    bc
        ld      a,(bc)  ;pivot
        ld      h,a
        dec     bc
        inc     de
fleft   inc     bc      ;do i++ while cur<piv
        ld      a,(bc)
        cp      h
        jp      c,fleft
fright  dec     de      ;do i-- while cur>piv
        ld      a,(de)
        ld      l,a
        ld      a,h
        cp      l
        jp      c,fright
        push    hl      ;save pivot
        ld      h,d     ;exit if lo>hi
        ld      l,e
        or      a
        sbc     hl,bc
        jp      c,next2
        ld      a,(bc)  ;swap (bc),(de)
        ld      h,a
        ld      a,(de)
        ld      (bc),a
        ld      a,h
        ld      (de),a
        pop     hl      ;restore pivot
        jp      fleft
next2   pop     hl      ;restore pivot
        pop     hl      ;pop lo
        push    bc      ;stack=left-hi
        ld      b,h
        ld      c,l     ;bc=lo,de=right
        jp      qsloop

TorqueScript[edit]

This is an implementation of Quicksort using script from the Torque game Builder (aka TorqueScript).

// Sorts unordered set %uSet, which must be of the class SimSet.
function Quicksort(%uSet)
{
    %less = new SimSet();
    %pivots = new SimSet();
    %greater = new SimSet();

    if(%uSet.getCount() <= 1)
        return %uSet;

    %pivotVal = %uSet.getObject(getRandom(0, %uSet.getCount()-1)).myValue;
    for(%i = 0; %i < %uSet.getCount(); %i ++)
    {
       // A new SimObject must be created in order to store it in a SimSet.
       %valObj = new SimObject(val)
       {
          myValue = %uSet.getObject(%i).myValue;
       };

        if(%pivotVal > %valObj.myValue)
            %less.add(%valObj);
        else if(%pivotVal == %valObj.myValue)
            %pivots.add(%valObj);
        else //if(%pivotVal < %valObj.myValue)
            %greater.add(%valObj);
    }

    return qConcatenate(Quicksort(%less), %pivots, Quicksort(%greater));
}

function qConcatenate(%less, %equal, %greater)
{
    %all = new SimSet();

    // Concatenate the three arrays, adding them to the SimSet one at a time.
    for(%i = 0; %i < %less.getCount(); %i ++)
    {
        %all.add(%less.getObject(%i));
    }
    for(%i = 0; %i < %equal.getCount(); %i ++)
    {
        %all.add(%equal.getObject(%i));
    }
    for(%i = 0; %i < %greater.getCount(); %i ++)
    {
        %all.add(%greater.getObject(%i));
    }

    return %all;
}

FORTRAN 90/95[edit]

This implementation of quicksort in FORTRAN 90/95 is non-recursive, and choose as pivot element the median of three (the first, last and middle element of the list). It also uses insertion sort to sort lists with less than 10 elements.

This implementation of Quicksort closely follows the one that can be found in the FORTRAN 90/95 GPL library AFNL.

! ***********************************
! *
  Subroutine Qsort(X, Ipt)
! *
! ***********************************
! * Sort Array X(:) in ascendent order 
! * If present Ipt, a pointer with the 
! * changes is returned in Ipt.
! ***********************************
 
    Type Limits
       Integer :: Ileft, Iright
    End Type Limits
 
    ! For a list with Isw number of elements or
    ! less use Insrt
    Integer, Parameter :: Isw = 10
 
    Real (kind=4), Intent (inout) :: X(:)
    Integer, Intent (out), Optional :: Ipt(:)
 
    Integer :: I, Ipvn, Ileft, Iright, ISpos, ISmax
    Integer, Allocatable :: IIpt(:)
    Type (Limits), Allocatable :: Stack(:)
 
 
    Allocate(Stack(Size(X)))
 
    Stack(:)%Ileft = 0
    If (Present(Ipt)) Then
       Forall (I=1:Size(Ipt)) Ipt(I) = I
 
       ! Iniitialize the stack
       Ispos = 1
       Ismax = 1
       Stack(ISpos)%Ileft  = 1
       Stack(ISpos)%Iright = Size(X)
 
       Do While (Stack(ISpos)%Ileft /= 0)
 
          Ileft = Stack(ISPos)%Ileft
          Iright = Stack(ISPos)%Iright
          If (Iright-Ileft <= Isw) Then
             CALL InsrtLC(X, Ipt, Ileft,Iright)
             ISpos = ISPos + 1
          Else
             Ipvn = ChoosePiv(X, Ileft, Iright)
             Ipvn = Partition(X, Ileft, Iright, Ipvn, Ipt)
 
             Stack(ISmax+1)%Ileft = Ileft
             Stack(ISmax+1) %Iright = Ipvn-1
             Stack(ISmax+2)%Ileft = Ipvn + 1
             Stack(ISmax+2)%Iright = Iright
             ISpos = ISpos + 1
             ISmax = ISmax + 2
          End If
       End Do
 
    Else
 
       ! Iniitialize the stack
       Ispos = 1
       Ismax = 1
       Stack(ISpos)%Ileft  = 1
       Stack(ISpos)%Iright = Size(X)
 
       Allocate(IIpt(10))
       Do While (Stack(ISpos)%Ileft /= 0)
!          Write(*,*)Ispos, ISmax
 
          Ileft = Stack(ISPos)%Ileft
          Iright = Stack(ISPos)%Iright
          If (Iright-Ileft <= Isw) Then
             CALL InsrtLC(X, IIpt, Ileft, Iright)
             ISpos = ISPos + 1
          Else
             Ipvn = ChoosePiv(X, Ileft, Iright)
             Ipvn = Partition(X, Ileft, Iright, Ipvn)
 
             Stack(ISmax+1)%Ileft = Ileft
             Stack(ISmax+1) %Iright = Ipvn-1
             Stack(ISmax+2)%Ileft = Ipvn + 1
             Stack(ISmax+2)%Iright = Iright
             ISpos = ISpos + 1
             ISmax = ISmax + 2
          End If
       End Do
       Deallocate(IIpt)
 
    End If
 
    Deallocate(Stack)
 
    Return
 
  CONTAINS
 
    ! ***********************************
    Integer Function ChoosePiv(XX, IIleft, IIright) Result (IIpv)
    ! ***********************************
    ! * Choose a Pivot element from XX(Ileft:Iright)
    ! * for Qsort. This routine chooses the median
    ! * of the first, last and mid element of the 
    ! * list.
    ! ***********************************
 
      Real (kind=4), Intent (in) :: XX(:)
      Integer, Intent (in) :: IIleft, IIright
 
      Real (kind=4) :: XXcp(3)
      Integer :: IIpt(3), IImd
 
      IImd = Int((IIleft+IIright)/2)
      XXcp(1) = XX(IIleft)
      XXcp(2) = XX(IImd)
      XXcp(3) = XX(IIright)
      IIpt = (/1,2,3/)
 
      CALL InsrtLC(XXcp, IIpt, 1, 3)
 
      Select Case (IIpt(2))
      Case (1)
         IIpv = IIleft
      Case (2)
         IIpv = IImd
      Case (3)
         IIpv = IIright
      End Select
 
      Return
    End Function ChoosePiv
 
    ! ***********************************
    Subroutine InsrtLC(XX, IIpt, IIl, IIr)
    ! ***********************************
    ! * Perform an insertion sort of the list 
    ! * XX(:) between index values IIl and IIr.
    ! * IIpt(:) returns the permutations
    ! * made to sort.
    ! ***********************************
 
      Real (kind=4), Intent (inout) :: XX(:)
      Integer, Intent (inout) :: IIpt(:)
      Integer, Intent (in) :: IIl, IIr
 
      Real (kind=4) :: RRtmp
      Integer :: II, JJ, IItmp
 
 
      Do II = IIl+1, IIr
         RRtmp = XX(II)
         Do JJ = II-1, 1, -1
            If (RRtmp < XX(JJ)) Then
               XX(JJ+1) = XX(JJ)
               CALL Swap_IN(IIpt, JJ, JJ+1)
            Else
               Exit
            End If
         End Do
         XX(JJ+1) = RRtmp
      End Do
 
      Return
    End Subroutine InsrtLC
 
  End Subroutine Qsort
 
! ***********************************
! *
  Integer Function Partition(X, Ileft, Iright, Ipv, Ipt) Result (Ipvfn)
! *
! ***********************************
! * This routine arranges the array X
! * between the index values Ileft and Iright
! * positioning elements smallers than
! * X(Ipv) at the left and the others 
! * at the right.
! * Internal routine used by Qsort.
! ***********************************
 
    Real (kind=4), Intent (inout) :: X(:)
    Integer, Intent (in) :: Ileft, Iright, Ipv
    Integer, Intent (inout), Optional :: Ipt(:)
 
    Real (kind=4) :: Rpv
    Integer :: I
 
    Rpv = X(Ipv)
    CALL Swap(X, Ipv, Iright)
    If (Present(Ipt)) CALL Swap_IN(Ipt, Ipv, Iright)
    Ipvfn = Ileft
 
    If (Present(Ipt))  Then
       Do I = Ileft, Iright-1
          If (X(I) <= Rpv) Then
             CALL Swap(X, I, Ipvfn)
             CALL Swap_IN(Ipt, I, Ipvfn)
             Ipvfn = Ipvfn + 1
          End If
       End Do
    Else
       Do I = Ileft, Iright-1
          If (X(I) <= Rpv) Then
             CALL Swap(X, I, Ipvfn)
             Ipvfn = Ipvfn + 1
          End If
       End Do
    End If
 
    CALL Swap(X, Ipvfn, Iright)
    If (Present(Ipt)) CALL Swap_IN(Ipt, Ipvfn, Iright)
 
    Return
  End Function Partition
 
! ***********************************
! *
  Subroutine Swap(X, I, J)
! *
! ***********************************
! * Swaps elements I and J of array X(:). 
! ***********************************
 
    Real (kind=4), Intent (inout) :: X(:)
    Integer, Intent (in) :: I, J
 
    Real (kind=4) :: Itmp
 
    Itmp = X(I)
    X(I) = X(J)
    X(J) = Itmp
 
    Return
  End Subroutine Swap
 
! ***********************************
! *
  Subroutine Swap_IN(X, I, J)
! *
! ***********************************
! * Swaps elements I and J of array X(:). 
! ***********************************
 
    Integer, Intent (inout) :: X(:)
    Integer, Intent (in) :: I, J
 
    Integer :: Itmp
 
    Itmp = X(I)
    X(I) = X(J)
    X(J) = Itmp
 
    Return
  End Subroutine Swap_IN

Retrieved from "http://en.wikibooks.org/w/index.php?title=Algorithm_Implementation/Sorting/Quicksort&oldid=2561536"

Category:

Algorithm Implementation

Hidden category:

Books to be merged